#include <boost/python.hpp>

#include <boost/algorithm/searching/boyer_moore.hpp>
#include <boost/container/map.hpp>

int kmp_search(char *source, char *pattern, bool print)
{
    int sLen = strlen(source);
    int pLen = strlen(pattern);

    if(sLen == 0 && pLen == 0) return 0;
    if(sLen == 0 || pLen == 0) return -1;
    if(pLen > sLen) return -1;

    int *match = new int[pLen];

    int index = 0;
    int i=1;
    int j=0;
    while(i < pLen)
    {
        if(pattern[0] == pattern[i])
        {
            match[i] = 1;
            for(j=0; j<i; j++)
            {
                match[index + j] = 0;
            }

            int k=1;
            while((i+k < pLen) && (pattern[k] == pattern[i+k]))
            {
                match[i+k] = k+1;
                k++;
            }

            i+=k;
            index = i;
        }else i++;
    }

    if(print)
    {
        for(j=0; j<pLen; j++)
        {
            printf("%c\t", pattern[j]);
        }
        printf("\n");
        for(j=0; j<pLen; j++)
        {
            printf("%d\t", match[j]);
        }
        printf("\n");
    }

    i=0;
    j=0;
    while(i<sLen)
    {
        if(source[i] != pattern[j]) i++;
        else
        {
            do
            {
                j++;
                i++;

                if(j<pLen && i < sLen)
                {
                    if(source[i] != pattern[j])
                    {
                        i += j;
                        j = match[j-1];
                        break;
                    }
                }else if(j == pLen)
                {
                    return i - j;
                }else if(i == sLen)
                {
                    return -1;
                }

            }while(true);

            j=0;
        }
    }


    return -1;
}


int bm_search(char *source, char *pattern, bool print)
{
    int sLen = strlen(source);
    int pLen = strlen(pattern);

    if(sLen == 0 && pLen == 0) return 0;
    if(sLen == 0 || pLen == 0) return -1;
    if(pLen > sLen) return -1;
    int *suffix = new int[pLen];
    boost::container::map<char, int> skip;

    //build skip
    for(int i=0; i<pLen; i++)
    {
        skip[pattern[i]] = i;
    }

    //build suffix
    int index = pLen-1;
    int i = pLen-2;
    int j = 0;
    while(i > -1)
    {
        if(pattern[pLen-1] == pattern[i])
        {
            suffix[i] = 1;
            for(j=0; j<i; j++)
            {
                suffix[index - j] = 0;
            }

            int k=1;
            while((i-k > -1) && (pattern[pLen-1-k] == pattern[i-k]))
            {
                suffix[i-k] = k+1;
                k++;
            }

            i-=k;
            index = i;
        }else i--;
    }

    if(print)
    {
        for(j=0; j<pLen; j++)
        {
            printf("%c\t", pattern[j]);
        }
        printf("\n");
        for(j=0; j<pLen; j++)
        {
            printf("%d\t", suffix[j]);
        }
        printf("\n");
    }

    i = pLen-1;
    j = 0;
    while(i < sLen)
    {
        if(pattern[pLen-1-j] == source[i-j])
        {
            if(pLen-1-j == 0) return i-j;
            j++;
        }else if(pattern[pLen-1-j] != source[i-j])
        {
            if(skip.find(source[i-j]) == skip.end())
            {
                i += (pLen-j);
                j = 0;
            }else
            {
                int m = pLen-1-j-skip[source[i-j]];
                int n = j - suffix[pLen-1-j];
                j = 0;
                if(m > n) i += m;
                else i += n;
            }
        }
    }

    return -1;
}


BOOST_PYTHON_MODULE(StringSearch)
{
    using namespace boost::python;

    def("kmp_search", kmp_search);
    def("bm_search", bm_search);
}
